package no33;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/19 0:01
 * 二叉搜索树的后序遍历序列
 * https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 */
public class Solution {

    public boolean verifyPostorder(int[] postorder) {
        // 边界
        if (postorder == null || postorder.length == 0) {
            return true;
        }
        return verify(postorder, 0, postorder.length-1);
    }

    // 判断 [start, end] 范围内是否符合二叉搜索树的后序序列
    private boolean verify(int[] postorder, int start, int end) {
        if (start >= end) {
            // 说明其他条件已经检索完了, 符合二叉搜索树的后序序列
            return true;
        }
        // 先找到二叉搜索树的根节点作为基准值
        int rootVal = postorder[end];
        // 如果符合二叉搜索树的后序序列
        // 则一定满足, 存在一个位置 index 使得左边的 val 都比 rootVal 小, 右边的都比 rootVal 大
        int index = start;
        while (index < end && postorder[index] < rootVal) {
            ++index;
        }
        // 检索 [index, end) 是否都比 rootVal 大, 不符合则不是二叉搜索树的后序序列
        for (int i = index; i < end; i++) {
            if (postorder[i] < rootVal) {
                return false;
            }
        }
        // 继续以 index 位置为根, 检索左右子树的后序序列是否符合
        return verify(postorder, start, index-1) && verify(postorder, index, end-1);
    }
}
